package com.skh.array;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;

/**
 * 数组的相对排序
 */
public class RelativeSortArray {

    /**
     * 给你两个数组，arr1 和 arr2，
     *
     * arr2 中的元素各不相同
     * arr2 中的每个元素都出现在 arr1 中
     * 对 arr1 中的元素进行排序，使 arr1 中项的相对顺序和 arr2 中的相对顺序相同。未在 arr2 中出现过的元素需要按照升序放在 arr1 的末尾。
     *
     *  
     *
     * 示例：
     *
     * 输入：arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6]
     * 输出：[2,2,2,1,4,3,3,9,6,7,19]
     *  
     *
     * 提示：
     *
     * arr1.length, arr2.length <= 1000
     * 0 <= arr1[i], arr2[i] <= 1000
     * arr2 中的元素 arr2[i] 各不相同
     * arr2 中的每个元素 arr2[i] 都出现在 arr1 中
     */

    /**
     * 自己实现的笨方法
     * @param arr1
     * @param arr2
     * @return
     */
    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        List<Integer> result = new ArrayList<>();
        List<Integer> arr1List = new ArrayList<>();
        for (int i : arr1) {
            arr1List.add(i);
        }

        for (int i : arr2) {
            Iterator<Integer> iterator = arr1List.iterator();
            while (iterator.hasNext()) {
                if (iterator.next().equals(i)) {
                    result.add(i);
                    iterator.remove();
                }
            }
        }
        Collections.sort(arr1List);
        for (Integer i : arr1List) {
            result.add(i);
        }

        int[] temp = new int[arr1.length];
        for (int i = 0; i < temp.length; i++) {
            temp[i] = result.get(i);
        }

        return temp;
    }

    /**
     * 思路:
     * 遍历arr1,统计每个元素的数量
     * 遍历arr2,处理arr2中出现的元素
     * 遍历nums,处理剩下arr2中未出现的元素
     * @param arr1
     * @param arr2
     * @return
     */
    public int[] relativeSortArray1(int[] arr1, int[] arr2) {
        int[] arr = new int[1001];
        int[] result = new int[arr1.length];
        for (int i = 0; i < arr1.length; i++) {
            arr[arr1[i]]++;
        }

        int index = 0;
        for (int i : arr2) {
            while (arr[i]-- > 0) {
                result[index++] = i;
            }
        }

        for (int i = 0; i < arr.length; i++) {
            while (arr[i]-- > 0) {
                result[index++] =i;
            }
        }


        return result;
    }

}
